package P121;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author DJ同学
 * @Date 2021/2/23 21:02
 * @Version 1.0
 * @Name 买卖股票的最佳时机
 * @Problem https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
 * @Idea 最大子序和
 * https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/solution/jiang-ti-mu-zhuan-huan-wei-zui-da-lian-xu-zi-shu-z/
 * 将题目转换成最大子序列
 * p[j]-p[i]
 * ==(p[j]-p[j-1])+(p[j-1]-p[j-2])+(p[j-2]-p[j-3])+...+(p[i+1]-p[i])
 * 经过上面的转化，我们就可以先求差值，然后求最大自序和
 */
public class Solution2 {
    @Test
    public void test(){
        int i = maxProfit(new int[]{7, 6, 4, 3, 1});
        System.out.println(i);
    }
    public int maxProfit(int[] prices) {
        int minIndex = 0;
        List<Integer> list = new ArrayList<>();
        for(int i=0;i<prices.length-1;i++){
            list.add(prices[i+1]-prices[i]);
        }
        int res = 0;
        int curSum = 0;
        for(int i = 0;i<list.size();i++){
            curSum+=list.get(i);
            if(curSum>res){
                res=curSum;
            }else if(curSum<0){
                curSum = 0;
            }
        }
        return res;
    }
}
